package vip.george.p0002;

/**
 * Definition for singly-linked list.
 */
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class P2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //头节点
        ListNode head = new ListNode(0);
        ListNode point = head;
        ListNode l1Point = l1;
        ListNode l2Point = l2;
        //每次相加的进位
        int carry = 0;
        while (l1Point != null || l2Point != null) {
            int sumValue = 0;
            if (l1Point != null) {
                sumValue += l1Point.val;
                l1Point = l1Point.next;
            }
            if (l2Point != null) {
                sumValue += l2Point.val;
                l2Point = l2Point.next;
            }
            // 结果相加，保留各位，然后进位
            sumValue = sumValue + carry;
            carry = sumValue / 10;
            point.next = new ListNode(sumValue % 10);
            point = point.next;
        }
        //如果最后一位有进位，则需要新增一个节点
        if (carry > 0) {
            point.next = new ListNode(carry);
            point = point.next;
        }
        return head.next;
    }

    public static void main(String[] args) {
        P2 p = new P2();
        ListNode l11 = new ListNode(2);
        ListNode l12 = new ListNode(4);
        ListNode l13 = new ListNode(3);
        ListNode l21 = new ListNode(5);
        ListNode l22 = new ListNode(6);
        ListNode l23 = new ListNode(4);
        l11.next = l12;
        l12.next = l13;
        l21.next = l22;
        l22.next = l23;
        ListNode result = p.addTwoNumbers(l11, l21);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        System.out.println();

        ListNode n11 = new ListNode(9);
        ListNode n12 = new ListNode(9);
        ListNode n13 = new ListNode(9);
        ListNode n14 = new ListNode(9);
        ListNode n15 = new ListNode(9);
        ListNode n16 = new ListNode(9);
        ListNode n17 = new ListNode(9);
        ListNode n21 = new ListNode(9);
        ListNode n22 = new ListNode(9);
        ListNode n23 = new ListNode(9);
        ListNode n24 = new ListNode(9);
        n11.next = n12;
        n12.next = n13;
        n13.next = n14;
        n14.next = n15;
        n15.next = n16;
        n16.next = n17;
        n21.next = n22;
        n22.next = n23;
        n23.next = n24;

        ListNode res = p.addTwoNumbers(n11, n21);
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }

    }
}
